class Node:
    def __init__(self, data=None, left=None, right=None, parent=None):
        self.data = data
        self.left = left
        self.right = right
        self.key = data
        self.parent = parent

    def preorder(self):
        print(self.data, end=' ')
        if self.left is not None:
            self.left.preorder()
        if self.right is not None:
            self.right.preorder()


class Tree:
    def __init__(self):
        self.root = None

    def insert_internal(self, node, middle=None):
        if middle is None:
            middle = self.root
        if middle.data < node.data:
            if middle.right is None:
                node.parent = middle
                middle.right = node
            else:
                self.insert_internal(node=node, middle=middle.right)
        else:
            if middle.right is None:
                node.parent = middle
                middle.left = node
            else:
                self.insert_internal(node=node, middle=middle.left)

    def insert_node(self, data=None):
        if data is None:
            return
        node = Node(data=data)
        if self.root is None:
            node.parent = None
            self.root = node
        else:
            self.insert_internal(node)

    def search_node(self, key, node):
        if node is None:
            return []
        if node is not None and key == node.key:
            return node.data
        elif node.left is not None:
            return self.search_node(key=key, node=node.left)
        elif node.right is not None:
            return self.search_node(key=key, node=node.right)

    def delete_node(self, key, node=None):
        if node is None:
            node = self.root
        if node is not None and key == node.key:
            self.right_node_replace(node)
        else:
            if node.left is not None and node.data > key:
                self.delete_node(key=key, node=node.left)
            elif node.right is not None and node.data < key:
                self.delete_node(key=key, node=node.right)

    def right_node_replace(self, node):
        parent_node = node.parent
        if node.right is not None:
            if node.left is not None:
                after_node_left = node.left
                no_left_node = self.search_node_left_none(node.right)
                no_left_node.left = after_node_left
            node = node.right
        else:
            node = node.left
        if parent_node is None:
            self.root = node
        else:
            if parent_node.data > node.data:
                parent_node.left = node
            else:
                parent_node.right = node
            node.parent = parent_node
            modify_root = self.search_node_parent(node)
            self.root = modify_root

    def search_node_parent(self, node):
        while node.parent is not None:
            node = node.parent
        return node

    def search_node_left_none(self, node):
        while node.left is not None:
            node = node.left
        return node


#            12
#           / \
#          9    30
#         / \   / \
#        3   10 13 32
def _check_binary_tree():
    tree = Tree()
    for x in [12, 9, 30, 3, 10, 13, 32]:
        tree.insert_node(x)
    tree.root.preorder()
    tree.delete_node(key=12)
    print()
    tree.root.preorder()


if __name__ == '__main__':
    _check_binary_tree()


